package leetcode;

public class ImplementStackUsingQueue {
    class LinkedListQueue {
        class Node {
            int val;
            Node next;

            public Node(int val, Node next) {
                this.val = val;
                this.next = next;
            }
        }

        Node head = new Node(-1, null);
        Node tail = head;
        int size = 0;

        {
            tail.next = head;
        }

        public void offer(int val) {
            Node added = new Node(val, head);
            tail.next = added;
            tail = added;
            size++;
        }

        public int poll() {
            if(isEmpty()){
                return -1;
            }
            Node first = head.next;
            head.next = first.next;
            if (first == tail) {
                tail = head;
            }
            size--;
            return first.val;
        }
        public int peek(){
            if(isEmpty()){
                return -1;
            }
            return head.next.val;
        }

        public boolean isEmpty() {
            return size == 0;
        }

    }
    LinkedListQueue queue = new LinkedListQueue();
    int size=0;
    public void push(int x) {
        queue.offer(x);
        for(int i=0;i<size;i++){
            queue.offer(queue.poll());
        }
        size++;
    }

    public int pop() {
        size--;
        return queue.poll();
        
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}
